import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length() ;
        Set<String> hash = new HashSet<>(wordDict);
        boolean[] dp = new boolean[len+1] ;
        s = " " + s ;
        dp[0] = true ;
        for(int i=1 ; i<=len ; i ++){
            for(int j=i ; j >=1 ; j--){
                if(dp[j-1] && hash.contains(s.substring(j , i+1))){
                    dp[i] = true ;
                    break ;
                }
            }
        }
        return dp[len];
    }
}